A sparse Johnson Lindenstrauss transform.
Recent work of [Dasgupta-Kumar-Sarlós, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010]. 1
A Sparse Johnson%2D%2DLindenstrauss Transform
Recent work of [Dasgupta-Kumar-Sarlós, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. The main ingredient in our proof is a spectral moment bound for quadratic forms that was recently used in [Diakonikolas-Kane-Nelson, FOCS 2010]. 1
Web Spam Detection via Commercial Intent Analysis.

Faster Least Squares Approximation

Link%2DBased Similarity Search to Fight Web Spam.
www.ilab.sztaki.hu/websearch We investigate the usability of similarity search in fighting Web spam based on the assumption that an unknown spam page is more similar to certain known spam pages than to honest pages. In order to be successful, search engine spam never appears in isolation: we observe link farms and alliances for the sole purpose of search engine ranking manipulation. The artificial nature and strong inside connectedness however gave rise to successful algorithms to identify search engine spam. One example is trust and distrust propagation, an idea originating in recommender systems and P2P networks, that yields spam classificators by spreading information along hyperlinks from white and blacklists. While most previous results use PageRank variants for propagation, we form classifiers by investigating similarity top lists of an unknown page along various measures such as co-citation, companion, nearest neighbors in low dimensional projections and SimRank. We test our method over two data sets previously used to measure spam filtering algorithms. 1.
Improved Approximation Algorithms for Large Matrices via Random Projections.
Recently several results appeared that show significant reduction in time for matrix multiplication, singular value decomposition as well as linear (ℓ2) regression, all based on data dependent random sampling. Our key idea is that low dimensional embeddings can be used to eliminate data dependence and provide more versatile, linear time pass efficient matrix computation. Our main contribution is summarized as follows. • Independent of the recent results of Har-Peled and of Deshpande and Vempala, one of the first – and to the best of our knowledge the most efficient – relative-error (1 + ɛ) �A − Ak � F approximation algorithms for the singular value decomposition of an m × n matrix A with M non-zero entries that requires 2 passes over the data and runs in time O M k
To randomize or not to randomize space optimal summaries for hyperlink analysis.
Personalized PageRank expresses link-based page quality around user selected pages in a similar way as PageRank expresses quality over the entire Web. The only previous personalized PageRank algorithm that can serve on-line queries for an unrestricted choice of pages on large graphs is our Monte Carlo algorithm [WAW 2004]; all earlier methods restrict the choice of personalization in some way. In this paper we achieve unrestricted personalization by combining rounding and randomized sketching techniques in the dynamic programming algorithm of Jeh and Widom [WWW 2003]. We evaluate the precision of approximation experimentally on large scale real-world data and find significant improvement over previous results. As a key theoretical contribution we show that our algorithms use an optimal amount of space by also improving earlier asymptotic worst-case lower bounds. Our lower bounds and algorithms apply to the SimRank link-based similarity function as well; of independent interest is the reduction of the SimRank computation to personalized PageRank.
SpamRank %2D%2D Fully Automatic Link Spam Detection.
Spammers intend to increase the PageRank of certain spam pages by creating a large number of links  pointing to them. We propose a novel method based on the concept of personalized PageRank that detects  pages with an undeserved high PageRank value without the need of any kind of white or blacklists or  other means of human intervention. We assume that spammed pages have a biased distribution of pages  that contribute to the undeserved high PageRank value. We define SpamRank by penalizing pages that  originate a suspicious PageRank share and personalizing PageRank on the penalties. Our method is  tested on a 31 M page crawl of the .de domain with a manually classified 1000-page stratified random  sample with bias towards large PageRank values.
On the feasibility of low%2Drank approximation for personalized PageRank.
Personalized PageRank expresses backlink-based page quality around user-selected pages in a similar way to PageRank over the entire Web. Algorithms for computing personalized PageRank on the fly are either limited to a restricted choice of page selection or believed to behave well only on sparser regions of the Web. In this paper we show the feasibility of computing personalized PageRank by a k  1000 lowrank approximation of the PageRank transition matrix; by our algorithm we may compute an approximate personalized PageRank by multiplying an n k, a k  n  matrix and the n-dimensional personalization vector. Since low-rank approximations are accurate on dense regions, we hope that our technique will combine well with known algorithms.
Towards Scaling Fully Personalized PageRank Algorithms

Searching a Small National Domain %2D Preliminary Report.

